<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xml:lang="en" lang="en">
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>Structure and Interpretation of Computer Programs, 2e: 3.2</title>

<meta name="description" content="Structure and Interpretation of Computer Programs, 2e: 3.2" />
<meta name="keywords" content="Structure and Interpretation of Computer Programs, 2e: 3.2" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<meta name="Generator" content="texi2any" />
<meta charset="utf-8" />
<link href="index.xhtml#Top" rel="start" title="Top" />
<link href="Term-Index.xhtml#Term-Index" rel="index" title="Term Index" />
<link href="index.xhtml#SEC_Contents" rel="contents" title="Table of Contents" />
<link href="Chapter-3.xhtml#Chapter-3" rel="prev" title="Chapter 3" />
<link href="3_002e3.xhtml#g_t3_002e3" rel="next" title="3.3" />
<link href="3_002e1.xhtml#g_t3_002e1_002e3" rel="prev" title="3.1.3" />

<link href="css/style.css" rel="stylesheet" type="text/css" />
<link href="css/prettify.css" rel="stylesheet" type="text/css" />

<script src="js/jquery.min.js" type="text/javascript"></script>
<script src="js/footnotes.js" type="text/javascript"></script>
<script src="js/browsertest.js" type="text/javascript"></script>
</head>

<body>
<section><span class="top jump" title="Jump to top"><a href="#pagetop" accesskey="t">⇡</a></span><a id="pagetop"></a><a id="g_t3_002e2"></a>
<nav class="header">
<p>
Next: <a href="3_002e3.xhtml#g_t3_002e3" accesskey="n" rel="next">3.3</a>, Prev: <a href="3_002e1.xhtml#g_t3_002e1" accesskey="p" rel="prev">3.1</a>, Up: <a href="Chapter-3.xhtml#Chapter-3" accesskey="u" rel="prev">Chapter 3</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>
<a id="The-Environment-Model-of-Evaluation"></a>
<h3 class="section"><span class="secnum">3.2</span><span class="sectitle">The Environment Model of Evaluation</span></h3>

<p>When we introduced compound procedures in <a href="Chapter-1.xhtml#Chapter-1">Chapter 1</a>, we used the
substitution model of evaluation (<a href="1_002e1.xhtml#g_t1_002e1_002e5">1.1.5</a>) to define what is meant
by applying a procedure to arguments:
</p>
<ul>
<li> To apply a compound procedure to arguments, evaluate the body of the procedure
with each formal parameter replaced by the corresponding argument.

</li></ul>

<p>Once we admit assignment into our programming language, such a definition is no
longer adequate.  In particular, <a href="3_002e1.xhtml#g_t3_002e1_002e3">3.1.3</a> argued that, in the
presence of assignment, a variable can no longer be considered to be merely a
name for a value.  Rather, a variable must somehow designate a “place” in
which values can be stored.  In our new model of evaluation, these places will
be maintained in structures called <a id="index-environments"></a>
<em>environments</em>.
</p>
<p>An environment is a sequence of <a id="index-frames"></a>
<em>frames</em>.  Each frame is a table
(possibly empty) of <a id="index-bindings"></a>
<em>bindings</em>, which associate variable names with
their corresponding values.  (A single frame may contain at most one binding
for any variable.)  Each frame also has a pointer to its <a id="index-enclosing-environment"></a>
<em>enclosing environment</em>, 
unless, for the purposes of discussion, the frame is considered
to be <a id="index-global-1"></a>
<em>global</em>.  The <a id="index-value-of-a-variable"></a>
<em>value of a variable</em> with respect to an
environment is the value given by the binding of the variable in the first
frame in the environment that contains a binding for that variable.  If no
frame in the sequence specifies a binding for the variable, then the variable
is said to be <a id="index-unbound"></a>
<em>unbound</em> in the environment.
</p>
<p><a href="#Figure-3_002e1">Figure 3.1</a> shows a simple environment structure consisting of three
frames, labeled I, II, and III.  In the diagram, A, B, C, and D are pointers to
environments.  C and D point to the same environment.  The variables <code>z</code>
and <code>x</code> are bound in frame II, while <code>y</code> and <code>x</code> are bound in
frame I.  The value of <code>x</code> in environment D is 3.  The value of <code>x</code>
with respect to environment B is also 3.  This is determined as follows: We
examine the first frame in the sequence (frame III) and do not find a binding
for <code>x</code>, so we proceed to the enclosing environment D and find the binding
in frame I.  On the other hand, the value of <code>x</code> in environment A is 7,
because the first frame in the sequence (frame II) contains a binding of
<code>x</code> to 7.  With respect to environment A, the binding of <code>x</code> to 7 in
frame II is said to <a id="index-shadow"></a>
<em>shadow</em> the binding of <code>x</code> to 3 in frame I.
</p>
<figure class="float">
<a id="Figure-3_002e1"></a>
<object style="width: 26.51ex; height: 23.31ex;" data="fig/chap3/Fig3.1b.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.1:</strong> A simple environment structure.</p>
</figcaption>
</figure>

<p>The environment is crucial to the evaluation process, because it determines the
context in which an expression should be evaluated.  Indeed, one could say that
expressions in a programming language do not, in themselves, have any meaning.
Rather, an expression acquires a meaning only with respect to some environment
in which it is evaluated.  Even the interpretation of an expression as
straightforward as <code>(+ 1 1)</code> depends on an understanding that one is
operating in a context in which <code>+</code> is the symbol for addition.  Thus, in
our model of evaluation we will always speak of evaluating an expression with
respect to some environment.  To describe interactions with the interpreter, we
will suppose that there is a global environment, consisting of a single frame
(with no enclosing environment) that includes values for the symbols associated
with the primitive procedures.  For example, the idea that <code>+</code> is the
symbol for addition is captured by saying that the symbol <code>+</code> is bound in
the global environment to the primitive addition procedure.
</p>

<a id="g_t3_002e2_002e1"></a>
<a id="The-Rules-for-Evaluation"></a>
<h4 class="subsection"><span class="secnum">3.2.1</span><span class="sectitle">The Rules for Evaluation</span></h4>

<p>The overall specification of how the interpreter evaluates a combination
remains the same as when we first introduced it in <a href="1_002e1.xhtml#g_t1_002e1_002e3">1.1.3</a>:
</p>
<ul>
<li> To evaluate a combination:

</li></ul>

<ol>
<li> Evaluate the subexpressions of the combination.<a class="footnote_link" id="DOCF140" href="#FOOT140"><sup>140</sup></a>

</li><li> Apply the value of the operator subexpression to the values of the operand
subexpressions.

</li></ol>

<p>The environment model of evaluation replaces the substitution model in
specifying what it means to apply a compound procedure to arguments.
</p>
<p>In the environment model of evaluation, a procedure is always a pair consisting
of some code and a pointer to an environment.  Procedures are created in one
way only: by evaluating a λ-expression.  This produces a procedure
whose code is obtained from the text of the λ-expression and whose
environment is the environment in which the λ-expression was
evaluated to produce the procedure.  For example, consider the procedure
definition
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">square x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x x</span><span class="clo">))</span></pre></div>

<p>evaluated in the global environment.  The procedure definition syntax is just
syntactic sugar for an underlying implicit λ-expression.  It would
have been equivalent to have used
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> square
  </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x x</span><span class="clo">)))</span></pre></div>

<p>which evaluates <code>(lambda (x) (* x x))</code> and binds <code>square</code> to the
resulting value, all in the global environment.
</p>
<p><a href="#Figure-3_002e2">Figure 3.2</a> shows the result of evaluating this <code>define</code> expression.
The procedure object is a pair whose code specifies that the procedure has one
formal parameter, namely <code>x</code>, and a procedure body <code>(* x x)</code>.  The
environment part of the procedure is a pointer to the global environment, since
that is the environment in which the λ-expression was evaluated to
produce the procedure. A new binding, which associates the procedure object
with the symbol <code>square</code>, has been added to the global frame.  In general,
<code>define</code> creates definitions by adding bindings to frames.
</p>
<figure class="float">
<a id="Figure-3_002e2"></a>
<object style="width: 33.85ex; height: 27.37ex;" data="fig/chap3/Fig3.2b.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.2:</strong> Environment structure produced by evaluating <code>(define (square x) (* x x))</code> in the global environment.</p>
</figcaption>
</figure>

<p>Now that we have seen how procedures are created, we can describe how
procedures are applied.  The environment model specifies: To apply a procedure
to arguments, create a new environment containing a frame that binds the
parameters to the values of the arguments.  The enclosing environment of this
frame is the environment specified by the procedure.  Now, within this new
environment, evaluate the procedure body.
</p>
<p>To show how this rule is followed, <a href="#Figure-3_002e3">Figure 3.3</a> illustrates the environment
structure created by evaluating the expression <code>(square 5)</code> in the global
environment, where <code>square</code> is the procedure generated in <a href="#Figure-3_002e2">Figure 3.2</a>.  
Applying the procedure results in the creation of a new environment,
labeled E1 in the figure, that begins with a frame in which <code>x</code>, the
formal parameter for the procedure, is bound to the argument 5.  The pointer
leading upward from this frame shows that the frame’s enclosing environment is
the global environment.  The global environment is chosen here, because this is
the environment that is indicated as part of the <code>square</code> procedure
object.  Within E1, we evaluate the body of the procedure, <code>(* x x)</code>.
Since the value of <code>x</code> in E1 is 5, the result is <code>(* 5 5)</code>, or 25.
</p>
<figure class="float">
<a id="Figure-3_002e3"></a>
<object style="width: 52.49ex; height: 27.37ex;" data="fig/chap3/Fig3.3b.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.3:</strong> Environment created by evaluating <code>(square 5)</code> in the global environment.</p>
</figcaption>
</figure>

<p>The environment model of procedure application can be summarized by two rules:
</p>
<ul>
<li> A procedure object is applied to a set of arguments by constructing a frame,
binding the formal parameters of the procedure to the arguments of the call,
and then evaluating the body of the procedure in the context of the new
environment constructed.  The new frame has as its enclosing environment the
environment part of the procedure object being applied.

</li><li> A procedure is created by evaluating a λ-expression relative to a
given environment.  The resulting procedure object is a pair consisting of the
text of the λ-expression and a pointer to the environment in which
the procedure was created.

</li></ul>

<p>We also specify that defining a symbol using <code>define</code> creates a binding in
the current environment frame and assigns to the symbol the indicated
value.<a class="footnote_link" id="DOCF141" href="#FOOT141"><sup>141</sup></a> Finally, we
specify the behavior of <code>set!</code>, the operation that forced us to introduce
the environment model in the first place.  Evaluating the expression
<code>(set! ⟨<var>variable</var>⟩ ⟨<var>value</var>⟩)</code> in some environment locates the
binding of the variable in the environment and changes that binding to indicate
the new value.  That is, one finds the first frame in the environment that
contains a binding for the variable and modifies that frame.  If the variable
is unbound in the environment, then <code>set!</code> signals an error.
</p>
<p>These evaluation rules, though considerably more complex than the substitution
model, are still reasonably straightforward.  Moreover, the evaluation model,
though abstract, provides a correct description of how the interpreter
evaluates expressions.  In <a href="Chapter-4.xhtml#Chapter-4">Chapter 4</a> we shall see how this model can
serve as a blueprint for implementing a working interpreter.  The following
sections elaborate the details of the model by analyzing some illustrative
programs.
</p>
<a id="g_t3_002e2_002e2"></a>
<a id="Applying-Simple-Procedures"></a>
<h4 class="subsection"><span class="secnum">3.2.2</span><span class="sectitle">Applying Simple Procedures</span></h4>

<p>When we introduced the substitution model in <a href="1_002e1.xhtml#g_t1_002e1_002e5">1.1.5</a> we showed how
the combination <code>(f 5)</code> evaluates to 136, given the following procedure
definitions:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">square x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x x</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sum-of-squares x y</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pln">square x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">square y</span><span class="clo">)))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">f a</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">sum-of-squares </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> a </span><span class="lit">1</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> a </span><span class="lit">2</span><span class="clo">)))</span></pre></div>

<p>We can analyze the same example using the environment model.  <a href="#Figure-3_002e4">Figure 3.4</a>
shows the three procedure objects created by evaluating the definitions of
<code>f</code>, <code>square</code>, and <code>sum-of-squares</code> in the global environment.
Each procedure object consists of some code, together with a pointer to the
global environment.
</p>
<figure class="float">
<a id="Figure-3_002e4"></a>
<object style="width: 54.14ex; height: 35.83ex;" data="fig/chap3/Fig3.4b.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.4:</strong> Procedure objects in the global frame.</p>
</figcaption>
</figure>

<p>In <a href="#Figure-3_002e5">Figure 3.5</a> we see the environment structure created by evaluating the
expression <code>(f 5)</code>.  The call to <code>f</code> creates a new environment E1
beginning with a frame in which <code>a</code>, the formal parameter of <code>f</code>, is
bound to the argument 5.  In E1, we evaluate the body of <code>f</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">sum-of-squares </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> a </span><span class="lit">1</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> a </span><span class="lit">2</span><span class="clo">))</span></pre></div>

<figure class="float">
<a id="Figure-3_002e5"></a>
<object style="width: 57.93ex; height: 31.17ex;" data="fig/chap3/Fig3.5b.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.5:</strong> Environments created by evaluating <code>(f 5)</code> using<!-- /@w --> the procedures in <a href="#Figure-3_002e4">Figure 3.4</a>.</p>
</figcaption>
</figure>

<p>To evaluate this combination, we first evaluate the subexpressions.  The first
subexpression, <code>sum-of-squares</code>, has a value that is a procedure object.
(Notice how this value is found: We first look in the first frame of E1, which
contains no binding for <code>sum-of-squares</code>.  Then we proceed to the
enclosing environment, i.e. the global environment, and find the binding shown
in <a href="#Figure-3_002e4">Figure 3.4</a>.)  The other two subexpressions are evaluated by applying
the primitive operations <code>+</code> and <code>*</code> to evaluate the two combinations
<code>(+ a 1)</code> and <code>(* a 2)</code> to obtain 6 and 10, respectively.
</p>
<p>Now we apply the procedure object <code>sum-of-squares</code> to the arguments 6 and
10.  This results in a new environment E2 in which the formal parameters
<code>x</code> and <code>y</code> are bound to the arguments.  Within E2 we evaluate the
combination <code>(+ (square x) (square y))</code>.  This leads us to evaluate
<code>(square x)</code>, where <code>square</code> is found in the global frame and
<code>x</code> is 6.  Once again, we set up a new environment, E3, in which <code>x</code>
is bound to 6, and within this we evaluate the body of <code>square</code>, which is
<code>(* x x)</code>.  Also as part of applying <code>sum-of-squares</code>, we must
evaluate the subexpression <code>(square y)</code>, where <code>y</code> is 10.  This
second call to <code>square</code> creates another environment, E4, in which
<code>x</code>, the formal parameter of <code>square</code>, is bound to 10.  And within E4
we must evaluate <code>(* x x)</code>.
</p>
<p>The important point to observe is that each call to <code>square</code> creates a new
environment containing a binding for <code>x</code>.  We can see here how the
different frames serve to keep separate the different local variables all named
<code>x</code>.  Notice that each frame created by <code>square</code> points to the global
environment, since this is the environment indicated by the <code>square</code>
procedure object.
</p>
<p>After the subexpressions are evaluated, the results are returned.  The values
generated by the two calls to <code>square</code> are added by <code>sum-of-squares</code>,
and this result is returned by <code>f</code>.  Since our focus here is on the
environment structures, we will not dwell on how these returned values are
passed from call to call; however, this is also an important aspect of the
evaluation process, and we will return to it in detail in <a href="Chapter-5.xhtml#Chapter-5">Chapter 5</a>.
</p>
<blockquote>
<p><strong><a id="Exercise-3_002e9"></a>Exercise 3.9:</strong> In <a href="1_002e2.xhtml#g_t1_002e2_002e1">1.2.1</a> we used the
substitution model to analyze two procedures for computing factorials, a
recursive version
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">factorial n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
      </span><span class="lit">1</span><span class="pln">
      </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> n </span><span class="opn">(</span><span class="pln">factorial </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">)))))</span></pre></div>

<p>and an iterative version
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">factorial n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">fact-iter </span><span class="lit">1</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> n</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">fact-iter product 
                   counter 
                   max-count</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&gt;</span><span class="pln"> counter max-count</span><span class="clo">)</span><span class="pln">
      product
      </span><span class="opn">(</span><span class="pln">fact-iter </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> counter product</span><span class="clo">)</span><span class="pln">
                 </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> counter </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
                 max-count</span><span class="clo">)))</span></pre></div>

<p>Show the environment structures created by evaluating <code>(factorial 6)</code>
using each version of the <code>factorial</code> procedure.<a class="footnote_link" id="DOCF142" href="#FOOT142"><sup>142</sup></a>
</p></blockquote>

<a id="g_t3_002e2_002e3"></a>
<a id="Frames-as-the-Repository-of-Local-State"></a>
<h4 class="subsection"><span class="secnum">3.2.3</span><span class="sectitle">Frames as the Repository of Local State</span></h4>

<p>We can turn to the environment model to see how procedures and assignment can
be used to represent objects with local state.  As an example, consider the
“withdrawal processor” from <a href="3_002e1.xhtml#g_t3_002e1_002e1">3.1.1</a> created by calling the
procedure
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-withdraw balance</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">amount</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&gt;=</span><span class="pln"> balance amount</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">begin</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> balance 
                     </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> balance amount</span><span class="clo">))</span><span class="pln">
               balance</span><span class="clo">)</span><span class="pln">
        </span><span class="str">"Insufficient funds"</span><span class="clo">)))</span></pre></div>

<p>Let us describe the evaluation of
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> W1 </span><span class="opn">(</span><span class="pln">make-withdraw </span><span class="lit">100</span><span class="clo">))</span></pre></div>

<p>followed by
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">W1 </span><span class="lit">50</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">50</span></i>
</pre></div>

<p><a href="#Figure-3_002e6">Figure 3.6</a> shows the result of defining the <code>make-withdraw</code>
procedure in the global environment.  This produces a procedure object that
contains a pointer to the global environment.  So far, this is no different
from the examples we have already seen, except that the body of the procedure
is itself a λ-expression.
</p>
<figure class="float">
<a id="Figure-3_002e6"></a>
<object style="width: 51.72ex; height: 36.87ex;" data="fig/chap3/Fig3.6c.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.6:</strong> Result of defining <code>make-withdraw</code> in the global environment.</p>
</figcaption>
</figure>

<p>The interesting part of the computation happens when we apply the procedure
<code>make-withdraw</code> to an argument:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> W1 </span><span class="opn">(</span><span class="pln">make-withdraw </span><span class="lit">100</span><span class="clo">))</span></pre></div>

<p>We begin, as usual, by setting up an environment E1 in which the formal
parameter <code>balance</code> is bound to the argument 100.  Within this
environment, we evaluate the body of <code>make-withdraw</code>, namely the
λ-expression.  This constructs a new procedure object, whose code
is as specified by the <code>lambda</code> and whose environment is E1, the
environment in which the <code>lambda</code> was evaluated to produce the procedure.
The resulting procedure object is the value returned by the call to
<code>make-withdraw</code>.  This is bound to <code>W1</code> in the global environment,
since the <code>define</code> itself is being evaluated in the global environment.
<a href="#Figure-3_002e7">Figure 3.7</a> shows the resulting environment structure.
</p>
<figure class="float">
<a id="Figure-3_002e7"></a>
<object style="width: 59.06ex; height: 40.41ex;" data="fig/chap3/Fig3.7b.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.7:</strong> Result of evaluating <code>(define W1 (make-withdraw 100))</code>.</p>
</figcaption>
</figure>

<p>Now we can analyze what happens when <code>W1</code> is applied to an argument:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">W1 </span><span class="lit">50</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">50</span></i>
</pre></div>

<p>We begin by constructing a frame in which <code>amount</code>, the formal parameter
of <code>W1</code>, is bound to the argument 50.  The crucial point to observe is
that this frame has as its enclosing environment not the global environment,
but rather the environment E1, because this is the environment that is
specified by the <code>W1</code> procedure object.  Within this new environment, we
evaluate the body of the procedure:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&gt;=</span><span class="pln"> balance amount</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">begin</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> balance </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> balance amount</span><span class="clo">))</span><span class="pln">
           balance</span><span class="clo">)</span><span class="pln">
    </span><span class="str">"Insufficient funds"</span><span class="clo">)</span></pre></div>

<p>The resulting environment structure is shown in <a href="#Figure-3_002e8">Figure 3.8</a>.  The
expression being evaluated references both <code>amount</code> and <code>balance</code>.
<code>Amount</code> will be found in the first frame in the environment, while
<code>balance</code> will be found by following the enclosing-environment pointer to
E1.
</p>
<figure class="float">
<a id="Figure-3_002e8"></a>
<object style="width: 58.97ex; height: 43.69ex;" data="fig/chap3/Fig3.8c.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.8:</strong> Environments created by applying the procedure object <code>W1</code>.</p>
</figcaption>
</figure>

<p>When the <code>set!</code> is executed, the binding of <code>balance</code> in E1 is
changed.  At the completion of the call to <code>W1</code>, <code>balance</code> is 50, and
the frame that contains <code>balance</code> is still pointed to by the procedure
object <code>W1</code>.  The frame that binds <code>amount</code> (in which we executed the
code that changed <code>balance</code>) is no longer relevant, since the procedure
call that constructed it has terminated, and there are no pointers to that
frame from other parts of the environment.  The next time <code>W1</code> is called,
this will build a new frame that binds <code>amount</code> and whose enclosing
environment is E1.  We see that E1 serves as the “place” that holds the local
state variable for the procedure object <code>W1</code>.  <a href="#Figure-3_002e9">Figure 3.9</a> shows the
situation after the call to <code>W1</code>.
</p>
<figure class="float">
<a id="Figure-3_002e9"></a>
<object style="width: 59.49ex; height: 32.72ex;" data="fig/chap3/Fig3.9b.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.9:</strong> Environments after the call to <code>W1</code>.</p>
</figcaption>
</figure>

<p>Observe what happens when we create a second “withdraw” object by making
another call to <code>make-withdraw</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> W2 </span><span class="opn">(</span><span class="pln">make-withdraw </span><span class="lit">100</span><span class="clo">))</span></pre></div>

<p>This produces the environment structure of <a href="#Figure-3_002e10">Figure 3.10</a>, which shows that
<code>W2</code> is a procedure object, that is, a pair with some code and an
environment.  The environment E2 for <code>W2</code> was created by the call to
<code>make-withdraw</code>.  It contains a frame with its own local binding for
<code>balance</code>.  On the other hand, <code>W1</code> and <code>W2</code> have the same code:
the code specified by the λ-expression in the body of
<code>make-withdraw</code>.<a class="footnote_link" id="DOCF143" href="#FOOT143"><sup>143</sup></a> We see here why <code>W1</code> and
<code>W2</code> behave as independent objects.  Calls to <code>W1</code> reference the
state variable <code>balance</code> stored in E1, whereas calls to <code>W2</code>
reference the <code>balance</code> stored in E2. Thus, changes to the local state of
one object do not affect the other object.
</p>
<figure class="float">
<a id="Figure-3_002e10"></a>
<object style="width: 59.66ex; height: 38.68ex;" data="fig/chap3/Fig3.10b.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.10:</strong> Using <code>(define W2 (make-withdraw 100))</code> to create a second object.</p>
</figcaption>
</figure>

<blockquote>
<p><strong><a id="Exercise-3_002e10"></a>Exercise 3.10:</strong> In the <code>make-withdraw</code>
procedure, the local variable <code>balance</code> is created as a parameter of
<code>make-withdraw</code>.  We could also create the local state variable
explicitly, using <code>let</code>, as follows:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-withdraw initial-amount</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">balance initial-amount</span><span class="clo">))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">amount</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&gt;=</span><span class="pln"> balance amount</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">begin</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> balance 
                       </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> balance amount</span><span class="clo">))</span><span class="pln">
                 balance</span><span class="clo">)</span><span class="pln">
          </span><span class="str">"Insufficient funds"</span><span class="clo">))))</span></pre></div>

<p>Recall from <a href="1_002e3.xhtml#g_t1_002e3_002e2">1.3.2</a> that <code>let</code> is simply syntactic sugar for a
procedure call:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">⟨</span><var><span class="pln">var</span></var><span class="pln">⟩ ⟨</span><var><span class="pln">exp</span></var><span class="pln">⟩</span><span class="clo">))</span><span class="pln"> ⟨</span><var><span class="pln">body</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>is interpreted as an alternate syntax for
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">((</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">⟨</span><var><span class="pln">var</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln"> ⟨</span><var><span class="pln">body</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln"> ⟨</span><var><span class="pln">exp</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>Use the environment model to analyze this alternate version of
<code>make-withdraw</code>, drawing figures like the ones above to illustrate the
interactions
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> W1 </span><span class="opn">(</span><span class="pln">make-withdraw </span><span class="lit">100</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">W1 </span><span class="lit">50</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> W2 </span><span class="opn">(</span><span class="pln">make-withdraw </span><span class="lit">100</span><span class="clo">))</span></pre></div>

<p>Show that the two versions of <code>make-withdraw</code> create objects with the same
behavior.  How do the environment structures differ for the two versions?
</p></blockquote>

<a id="g_t3_002e2_002e4"></a>
<a id="Internal-Definitions"></a>
<h4 class="subsection"><span class="secnum">3.2.4</span><span class="sectitle">Internal Definitions</span></h4>

<p>Section <a href="1_002e1.xhtml#g_t1_002e1_002e8">1.1.8</a> introduced the idea that procedures can have internal
definitions, thus leading to a block structure as in the following procedure to
compute square roots:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sqrt x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">good-enough? guess</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pun">&lt;</span><span class="pln"> </span><span class="opn">(</span><span class="pln">abs </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> </span><span class="opn">(</span><span class="pln">square guess</span><span class="clo">)</span><span class="pln"> x</span><span class="clo">))</span><span class="pln"> </span><span class="lit">0.001</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">improve guess</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">average guess </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> x guess</span><span class="clo">)))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sqrt-iter guess</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">good-enough? guess</span><span class="clo">)</span><span class="pln">
        guess
        </span><span class="opn">(</span><span class="pln">sqrt-iter </span><span class="opn">(</span><span class="pln">improve guess</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">sqrt-iter </span><span class="lit">1.0</span><span class="clo">))</span></pre></div>

<p>Now we can use the environment model to see why these internal definitions
behave as desired.  <a href="#Figure-3_002e11">Figure 3.11</a> shows the point in the evaluation of the
expression <code>(sqrt 2)</code> where the internal procedure <code>good-enough?</code> has
been called for the first time with <code>guess</code> equal to 1.
</p>
<figure class="float">
<a id="Figure-3_002e11"></a>
<object style="width: 60.01ex; height: 56.90ex;" data="fig/chap3/Fig3.11b.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.11:</strong> <code>Sqrt</code> procedure with internal definitions.</p>
</figcaption>
</figure>

<p>Observe the structure of the environment.  <code>Sqrt</code> is a symbol in the
global environment that is bound to a procedure object whose associated
environment is the global environment.  When <code>sqrt</code> was called, a new
environment E1 was formed, subordinate to the global environment, in which the
parameter <code>x</code> is bound to 2.  The body of <code>sqrt</code> was then evaluated
in E1.  Since the first expression in the body of <code>sqrt</code> is
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">good-enough? guess</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pun">&lt;</span><span class="pln"> </span><span class="opn">(</span><span class="pln">abs </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> </span><span class="opn">(</span><span class="pln">square guess</span><span class="clo">)</span><span class="pln"> x</span><span class="clo">))</span><span class="pln"> </span><span class="lit">0.001</span><span class="clo">))</span></pre></div>

<p>evaluating this expression defined the procedure <code>good-enough?</code>  in the
environment E1.  To be more precise, the symbol <code>good-enough?</code> was added
to the first frame of E1, bound to a procedure object whose associated
environment is E1.  Similarly, <code>improve</code> and <code>sqrt-iter</code> were defined
as procedures in E1.  For conciseness, <a href="#Figure-3_002e11">Figure 3.11</a> shows only the
procedure object for <code>good-enough?</code>.
</p>
<p>After the local procedures were defined, the expression <code>(sqrt-iter 1.0)</code>
was evaluated, still in environment E1.  So the procedure object bound to
<code>sqrt-iter</code> in E1 was called with 1 as an argument.  This created an
environment E2 in which <code>guess</code>, the parameter of <code>sqrt-iter</code>, is
bound to 1.  <code>Sqrt-iter</code> in turn called <code>good-enough?</code> with the value
of <code>guess</code> (from E2) as the argument for <code>good-enough?</code>.  This set up
another environment, E3, in which <code>guess</code> (the parameter of
<code>good-enough?</code>) is bound to 1.  Although <code>sqrt-iter</code> and
<code>good-enough?</code> both have a parameter named <code>guess</code>, these are two
distinct local variables located in different frames.  Also, E2 and E3 both
have E1 as their enclosing environment, because the <code>sqrt-iter</code> and
<code>good-enough?</code> procedures both have E1 as their environment part.  One
consequence of this is that the symbol <code>x</code> that appears in the body of
<code>good-enough?</code> will reference the binding of <code>x</code> that appears in E1,
namely the value of <code>x</code> with which the original <code>sqrt</code> procedure was
called.
</p>
<p>The environment model thus explains the two key properties that make local
procedure definitions a useful technique for modularizing programs:
</p>
<ul>
<li> The names of the local procedures do not interfere with names external to the
enclosing procedure, because the local procedure names will be bound in the
frame that the procedure creates when it is run, rather than being bound in the
global environment.

</li><li> The local procedures can access the arguments of the enclosing procedure,
simply by using parameter names as free variables.  This is because the body of
the local procedure is evaluated in an environment that is subordinate to the
evaluation environment for the enclosing procedure.

</li></ul>

<blockquote>
<p><strong><a id="Exercise-3_002e11"></a>Exercise 3.11:</strong> In <a href="#g_t3_002e2_002e3">3.2.3</a> we saw how
the environment model described the behavior of procedures with local state.
Now we have seen how internal definitions work.  A typical message-passing
procedure contains both of these aspects.  Consider the bank account procedure
of <a href="3_002e1.xhtml#g_t3_002e1_002e1">3.1.1</a>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-account balance</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">withdraw amount</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&gt;=</span><span class="pln"> balance amount</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">begin</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> balance 
                     </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> balance 
                        amount</span><span class="clo">))</span><span class="pln">
               balance</span><span class="clo">)</span><span class="pln">
        </span><span class="str">"Insufficient funds"</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">deposit amount</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> balance </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> balance amount</span><span class="clo">))</span><span class="pln">
    balance</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">dispatch m</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> m </span><span class="lit">'withdraw</span><span class="clo">)</span><span class="pln"> withdraw</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> m </span><span class="lit">'deposit</span><span class="clo">)</span><span class="pln"> deposit</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Unknown request: 
                        MAKE-ACCOUNT"</span><span class="pln"> 
                       m</span><span class="clo">))))</span><span class="pln">
  dispatch</span><span class="clo">)</span></pre></div>

<p>Show the environment structure generated by the sequence of interactions
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> acc </span><span class="opn">(</span><span class="pln">make-account </span><span class="lit">50</span><span class="clo">))</span><span class="pln">

</span><span class="opn">((</span><span class="pln">acc </span><span class="lit">'deposit</span><span class="clo">)</span><span class="pln"> </span><span class="lit">40</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">90</span></i><span class="pln">

</span><span class="opn">((</span><span class="pln">acc </span><span class="lit">'withdraw</span><span class="clo">)</span><span class="pln"> </span><span class="lit">60</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">30</span></i>
</pre></div>

<p>Where is the local state for <code>acc</code> kept?  Suppose we define another
account
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> acc2 </span><span class="opn">(</span><span class="pln">make-account </span><span class="lit">100</span><span class="clo">))</span></pre></div>

<p>How are the local states for the two accounts kept distinct?  Which parts of
the environment structure are shared between <code>acc</code> and <code>acc2</code>?
</p></blockquote>

<div class="footnote">
<h4 class="footnotes-heading">Footnotes</h4>

<div id="FOOT140"><p><a class="footnote_backlink" href="#DOCF140"><sup>140</sup></a>
Assignment introduces a
subtlety into step 1 of the evaluation rule.  As shown in <a href="3_002e1.xhtml#Exercise-3_002e8">Exercise 3.8</a>,
the presence of assignment allows us to write expressions that will produce
different values depending on the order in which the subexpressions in a
combination are evaluated.  Thus, to be precise, we should specify an
evaluation order in step 1 (e.g., left to right or right to left).  However,
this order should always be considered to be an implementation detail, and one
should never write programs that depend on some particular order.  For
instance, a sophisticated compiler might optimize a program by varying the
order in which subexpressions are evaluated.</p>
</div>
<div id="FOOT141"><p><a class="footnote_backlink" href="#DOCF141"><sup>141</sup></a>
If there is already a binding for the variable in the current
frame, then the binding is changed.  This is convenient because it allows
redefinition of symbols; however, it also means that <code>define</code> can be used
to change values, and this brings up the issues of assignment without
explicitly using <code>set!</code>.  Because of this, some people prefer
redefinitions of existing symbols to signal errors or warnings.</p>
</div>
<div id="FOOT142"><p><a class="footnote_backlink" href="#DOCF142"><sup>142</sup></a>
The environment
model will not clarify our claim in <a href="1_002e2.xhtml#g_t1_002e2_002e1">1.2.1</a> that the interpreter
can execute a procedure such as <code>fact-iter</code> in a constant amount of space
using tail recursion.  We will discuss tail recursion when we deal with the
control structure of the interpreter in <a href="5_002e4.xhtml#g_t5_002e4">5.4</a>.</p>
</div>
<div id="FOOT143"><p><a class="footnote_backlink" href="#DOCF143"><sup>143</sup></a>
Whether <code>W1</code> and <code>W2</code> share the same
physical code stored in the computer, or whether they each keep a copy of the
code, is a detail of the implementation.  For the interpreter we implement in
<a href="Chapter-4.xhtml#Chapter-4">Chapter 4</a>, the code is in fact shared.</p>
</div>
</div>
<nav class="header">
<p>
Next: <a href="3_002e3.xhtml#g_t3_002e3" accesskey="n" rel="next">3.3</a>, Prev: <a href="3_002e1.xhtml#g_t3_002e1" accesskey="p" rel="prev">3.1</a>, Up: <a href="#g_t3_002e2" accesskey="u" rel="prev">3.2</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>


</section><span class="bottom jump" title="Jump to bottom"><a href="#pagebottom" accesskey="b">⇣</a></span><a id="pagebottom"></a>
</body>
</html>